package com.simon.study.algorithm.basic;

import java.util.Arrays;

/**
 * <p>
 *
 * @author simon
 * @date 2022/8/20 10:16 下午
 */
public class AllReview {

    public static void main(String[] args) {
        int[] arr = {2, 5, 4, 1, 4, 8, 9, 6, 3, 4, 1};
        quickSort(arr, 0, arr.length-1);

        System.out.println(Arrays.toString(arr));


        arr = new int[]{2, 1, 8, 5, 6, 7, 10, 2, 5, 4, 1};

        bubble(arr, 4, 8);
        System.out.println(Arrays.toString(arr));

        bubble(arr, 0, arr.length);
        System.out.println(Arrays.toString(arr));

        arr = new int[]{2, 1, 8, 6, 3, 7, 10, 2, 5, 4, 1};
        select(arr, 3, 7);
        System.out.println(Arrays.toString(arr));
        select(arr, 0, arr.length);
        System.out.println(Arrays.toString(arr));

        arr = new int[]{2, 1, 8, 5, 6, 7, 10, 2, 5, 4, 1};
        insert(arr, 2, 5);
        System.out.println(Arrays.toString(arr));

        insert(arr, 0, arr.length);
        System.out.println(Arrays.toString(arr));


        arr = new int[]{8, 3, 7, 3, 4, 10, 9, 11, 2, 1, 11};
        mergeSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));

        arr = new int[]{1, 2, 3, 4, 5, 6, 8, 10, 11, 13, 16, 18};
        System.out.println( recursiveSearch(arr, 0, arr.length-1, 0) );
        System.out.println( recursiveSearch(arr, 0, arr.length-1, 19) );
        System.out.println( recursiveSearch(arr, 0, arr.length-1, 1) );
        System.out.println( recursiveSearch(arr, 0, arr.length-1, 18) );
        System.out.println( recursiveSearch(arr, 0, arr.length-1, 3) );
        System.out.println( recursiveSearch(arr, 0, arr.length-1, 10) );
        System.out.println( recursiveSearch(arr, 0, arr.length-1, 13) );
        System.out.println( recursiveSearch(arr, 0, arr.length-1, 4) );
        System.out.println( recursiveSearch(arr, 0, arr.length-1, 6) );

        System.out.println( binarySearch(arr, 0, arr.length-1, 0) );
        System.out.println( binarySearch(arr, 0, arr.length-1, 19) );
        System.out.println( binarySearch(arr, 0, arr.length-1, 1) );
        System.out.println( binarySearch(arr, 0, arr.length-1, 18) );
        System.out.println( binarySearch(arr, 0, arr.length-1, 3) );
        System.out.println( binarySearch(arr, 0, arr.length-1, 10) );
        System.out.println( binarySearch(arr, 0, arr.length-1, 13) );
        System.out.println( binarySearch(arr, 0, arr.length-1, 4) );
        System.out.println( binarySearch(arr, 0, arr.length-1, 6) );
    }


    public static void quickSort(int[] arr, int as, int ae){
        if( as >= ae ){ return; }

        int t = as + (int)((ae-as)*Math.random());

        int[] ps = partition(arr, as, ae, t);
        if(ps[0] > as){ quickSort(arr, as, ps[0]); }
        if(ps[1] < ae){ quickSort(arr, ps[1], ae); }
    }


    public static int[] partition(int[] arr, int as, int ae, int idx){
        int ap = as, left = as, num = arr[idx], right = ae, ec = 0;

        while (ap <= right){
            if(arr[ap] < num && left++ < ap++){ swap(arr, left-1, ap-1); }
            else if(arr[ap] == num){ ap++; ec++; }
            else if(arr[ap]  > num){ if(ap == right){ break; } swap(arr, ap, right--); }
        }

        return new int[]{left-1, left + ec};
    }


    public static void select(int[] arr, int as, int ae){
        if(ae > (arr.length-1)){ ae = arr.length-1; }

        for (int i = as; i < ae; i++) {
            for (int j = i; j < ae; j++) {
                if(arr[i] > arr[j+1]){ swap(arr, i, j+1); }
            }
        }
    }

    public static void insert(int[] arr, int as, int ae){
        if(ae > (arr.length-1)){ ae = arr.length-1; }

        for (int i = as; i < ae; i++) {
            for (int j = i+1; j > as; j--) {
                if(arr[j] < arr[j-1]){ swap(arr, j, j-1); }else { break; }
            }
        }
    }

    public static void bubble(int[] arr, int as, int ae){
        if(ae > (arr.length-1)){ ae = arr.length-1; }

        for (int i = as; i < ae; i++) {
            for (int j = as; j < ae-i+as; j++) {
                if(arr[j] > arr[j+1]){ swap(arr, j, j+1); }
            }
        }
    }

    public static void mergeSort(int[] arr, int as, int ae){
        if(as >= ae){ return; }

        int mid = as + ((ae-as)/2);

        mergeSort(arr, as, mid);
        mergeSort(arr, mid+1, ae);
        merge(arr, as, ae, mid);
    }

    public static void merge(int[] arr, int as, int ae, int mid){
        int lp = as, mp = mid+1, idx=0;

        int size  = ae-as+1;
        if(size < 4){ insert(arr, as, ae); return; }

        int[] dup = new int[ae-as+1];

        while (lp <= mid && mp <= ae){
            dup[idx++] = arr[lp] < arr[mp] ? arr[lp++] : arr[mp++];
        }

        while (lp <= mid){ dup[idx++] = arr[lp++]; }
        while (mp <= ae ){ dup[idx++] = arr[mp++]; }

        for (int i = 0; i < dup.length; i++) { arr[as+i] = dup[i]; }
    }

    public static void swap(int[] arr, int i, int j){
        if( i==j ){ return; }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }


    public static int recursiveSearch(int[] arr, int as, int ae, int num){
        if(as > ae){ return -1; }
        int mid = as + ((ae-as)/2);

        if(arr[mid] == num){ return mid; }
        else if(arr[mid] > num){ return recursiveSearch(arr, as, mid-1, num); }
        else{ return recursiveSearch(arr, mid+1, ae, num); }
    }


    public static int binarySearch(int[] arr, int as, int ae, int num){
        int lp = as, rp = ae, mid;

        while (lp <= rp){
            mid = lp + ((rp-lp)/2);

            if(arr[mid] == num){ return mid; }
            else if(arr[mid] > num){ rp = mid-1; }
            else{ lp = mid + 1; }
        }
        return -1;
    }


    public static void shellShort(int[] arr, int n){
        for (int d = n/2; d > 0; d /= 2) {
            for(int i=d; i<n; i ++){
                int num = arr[i], j = i;
                for(; j >= d && num < arr[j-d]; j -= d){
                    arr[j] = arr[j-d];
                }

                arr[j] = num;
            }
        }
    }
}
